public class No019 {
    /**
     * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
     * 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
     * 在本题中，匹配是指字符串的所有字符匹配整个模式。
     * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
     */
    public static void main(String[] args) {
        System.out.println(match(new char[]{'a', 'b'}, new char[]{'a', '*', 'b'}));
    }

    public static boolean match(char[] str, char[] pattern) {
        return matchCore(str, pattern, 0, 0);
    }

    public static boolean matchCore(char[] str, char[] pattern, int strIndex, int patternIndex) {
        if (strIndex == str.length && patternIndex == pattern.length) return true;
        if (strIndex < str.length && patternIndex == pattern.length) return false;
        // 模式串下一个是 *
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            // 当前字符匹配成功
            if (strIndex < str.length && (str[strIndex] == pattern[patternIndex] || pattern[patternIndex] == '.')) {
                return matchCore(str, pattern, strIndex + 1, patternIndex + 2) // * 使当前字符出现1次
                        || matchCore(str, pattern, strIndex + 1, patternIndex)              // * 使当前字符出现2次
                        || matchCore(str, pattern, strIndex, patternIndex + 2);         // * 使当前字符出现0次
            }
            //未匹配成功，只能使当前字符出现0次
            else {
                return matchCore(str, pattern, strIndex, patternIndex + 2);
            }
        }
        // 下一个不是* ，匹配成功
        if (strIndex < str.length && (str[strIndex] == pattern[patternIndex] || pattern[patternIndex] == '.')) {
            return matchCore(str, pattern, strIndex + 1, patternIndex + 1);
        }
        // 匹配失败
        return false;
    }
}
